package main

import (
	"fmt"
	common "leetcode/tree/common"
)

func sumOfLeftLeaves(root *common.TreeNode) int {
	var res int
	type data struct {
		node *common.TreeNode
		pos  int // -1 left 0 root 1 right
	}
	var queue []data
	queue = append(queue, data{node: root, pos: 0})
	for len(queue) != 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			head := queue[0]
			queue = queue[1:]
			if head.pos == -1 && head.node.Left == nil && head.node.Right == nil {
				res += head.node.Val
				continue
			}
			if head.node.Left != nil {
				queue = append(queue, data{node: head.node.Left, pos: -1})
			}
			if head.node.Right != nil {
				queue = append(queue, data{node: head.node.Right, pos: 1})
			}
		}
	}
	return res
}

func dfs(node *common.TreeNode, pos int, res *int) {
	if pos == -1 && node.Left == nil && node.Right == nil {
		*res += node.Val
		return
	}
	if node.Left != nil {
		dfs(node.Left, -1, res)
	}
	if node.Right != nil {
		dfs(node.Right, 1, res)
	}
}

func main() {
	root := common.TreeNode{Val: 3}
	node9 := common.TreeNode{Val: 9}
	node20 := common.TreeNode{Val: 20}
	node15 := common.TreeNode{Val: 15}
	node7 := common.TreeNode{Val: 7}
	root.Left = &node9
	root.Right = &node20
	node20.Left = &node15
	node20.Right = &node7
	fmt.Println(sumOfLeftLeaves(&root))
	var res int
	dfs(&root, 0, &res)
	fmt.Println(res)
}
